import java.util.Deque;
import java.util.LinkedList;

class Solution3 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int left = 0;
        int right = 0;
        int size = nums.length;
        int[] ret = new int[nums.length-2];
        int index = 0;
        //建立第一个窗口
        for (;right < k && right < size;right++){
            if(right == 0){
                //第一个直接加
                deque.addFirst(nums[right]);
            } else {
                //如果这个数大，就把队列中的数全都换成他
                if(deque.peekFirst() < nums[right]){
                    int Tsize = 0;
                    while (!deque.isEmpty() && deque.peekFirst() < nums[right]){
                        deque.pollLast();
                        Tsize++;
                    }
                    while (Tsize > 0){
                        deque.addFirst(nums[right]);
                        Tsize--;
                    }
                    deque.addFirst(nums[right]);
                }
            }
        }
        //窗口移动
        while (right < size){
            ret[index++] = deque.pollLast();
            //判断待加入数字的大小
            if(deque.peekFirst() < nums[right] ){
                int Tsize = 0;
                while (!deque.isEmpty() && deque.peekFirst() < nums[right]){
                    deque.pollLast();
                    Tsize++;
                }
                while (Tsize > 0){
                    deque.addFirst(nums[right]);
                    Tsize--;
                }
                deque.addFirst(nums[right]);
            } else {
                deque.addFirst(nums[right]);
            }
            right++;
        }
        return ret;
    }

    public static void main(String[] args) {
        Solution3 s = new Solution3();
        int[] r = {2,3,4,2,6,2,5,1};
        int[] ret = s.maxSlidingWindow(r,3);
        System.out.println(ret);
    }
}